Find All Anagrams in a String

Try to solve the Find All Anagrams in a String problem.

We'll cover the following

Statement#

Given two strings, a and b, return an array of all the start indexes of anagrams of b in a. We may return the answer in any order.

An anagram is a word or phrase created by rearranging the letters of another word or phrase while utilizing each of the original letters exactly once. For example, “act” is the anagram of “cat”, and “flow” is the anagram of “wolf”.

Constraints:

  • 1≤1\leq a.length, b.length ≤3×103\leq 3 \times 10^3
  • Both a and b consist only of lowercase English letters.

Examples#

Created with Fabric.js 3.6.6 string a h e l l o string b h e l l Input 1 Input 2 Output 0 Sample example 1 To find all the anagrams of string b in string a, we look for characters of string b in string a. The characters can be in any order but should be consecutive. The substring with a start index of 0 in string a is "hell", which is an anagram of string b that we are looking for, "hell".

1 of 3

Created with Fabric.js 3.6.6 string a h e l l o Input 1 Input 2 Output string b o l 3 Sample example 2 To find all the anagrams of string b in string a, we look for characters of string b in string a. The characters can be in any order but should be consecutive, and each letter should have the same frequency as the original string. The substring with a start index of 3 in string a is "lo", which is an anagram of string b that we are looking for, "ol".

2 of 3

Created with Fabric.js 3.6.6 string a h e l l o Input 1 Input 2 Output string b l l Sample example 3 2 Let's take a look at another scenario where string bappears twice in string a, but we would count it as asingle occurrence of an anagram because the two permutations of "ll" are identical. We will return the start index of the substring in string a. In this case that's 2, which would be the output.

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you to check if you’re solving the correct problem:

Find All Anagrams in a String

5

What are all the anagrams of string b in string a if the following inputs are given?

a = “teaateat”

b = “eat”

Your Answer
A)

“aet” (starts from index 2)

“eta” (starts from index 5)

“tae” (starts from index 7)

Explanation

We need anagrams only in the forward direction of string a and not in the reverse direction. All the given anagrams are invalid.

B)

“tea” (starts from index 1)

“ate” (starts from index 4)

“tea” (starts from index 5)

“eat” (starts from index 6)

Correct Answer
C)

“tea” (starts from index 0)

“ate” (starts from index 3)

“tea” (starts from index 4)

“eat” (starts from index 5)

Explanation

These are the only four anagrams of string b in string a.

D)

“tea” (starts from index 1)

“tae” (starts from index 7)

Question 5 of 55 attempted

Figure it out#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Create two hash maps, hash_a and hash_b, acting as counters. hash_b stores the frequency of characters in string b, and hash_a stores the count of characters in the sliding window inside the string a.

While traversing string a, if (at any point) hash_a equals hash_b, it means we found an anagram. Therefore, add the index of the first character of the current sliding window to the output array.

After traversing the entire string a, return the array of all the start indexes of the anagrams of string b in string a as the output.

Otherwise, if we don’t find any anagrams of string b in string a, return an empty array.

Try it yourself#

Implement your solution in main.py in the following coding playground. We've provided a useful code template in the other file that you may build on to solve this problem.

Python
main.py
freq_track.py
Powered by AI
Input #1
Input #2
Find All Anagrams in a String

Solution: First Unique Character in a String

Solution: Find All Anagrams in a String